本篇內容

• 介紹Lex的token標記
• 範例 - 簡易計算機1 (1 of 3)

前言

我們前面介紹了Yacc的運作原理與流程，以及BNF表示式。
接下來，我們就可以來做一個簡單的小型的Parser，並從其中學習Yacc的語法。

在前幾天我們已經介紹過Lex這個分析文本與標記token的工具。然而，在之前的範例中，我們只有實作”分類”的部分，沒有標記token。這是因為Lex標記文字後會交給Yacc進行語法分析，而我們那時候還沒介紹Yacc。現在，在進入Yacc之前，我們先從Lex開始，簡單複習一下之前的內容，並介紹Lex的另一項功能 - 標記token。

標記token

我們在用Lex讀取文本時，若要讓Yacc進行語法判斷，便需要把分類好的字串作標記。

例如，今天我如果要在Yacc作下面的加法運算：

1 + 2

我需要先辨識出：

1. 數字 (要相加的兩數)
2. 運算符號 (加號)

因此，在Yacc比對規則之前，我需要把1跟2標記為”數字”，將+號標記為”加號”

標記的方式很簡單：先為標記的token命名，然後直接return即可。

以剛剛的例子來說，標記完的結果如下：

{posint}        { yylval = atoi(yytext); return NUMBER; }
"+"             { return yytext[0]; }

為什麼這些token的變數名稱不需要先宣告呢?

其實是要的，只不過定義的地方在Yacc檔案中。前天有稍微提過，在編譯的過程中，Yacc會先被編譯，生出的C檔案內含有token定義，這個C檔案再與Lex編譯。因此，我們在寫到Yacc檔案時才會做這件事。

接著，我們來看數字與加法符號的token標記。

首先是數字。由於之後的加法在C++中是兩個int的運算，因此在這裡我們就要先將字串轉成int。在Lex中，我們可以使用yylval來儲存我們想要的變數型別。在本例中，我們想要用yylval存入int型別的變數，所以我們需要將yylval的型別宣告為int：

#define YYSTYPE int

如此一來，當我們讀取到一個整數時，我們便可以將其標記為”NUMBER”，並將值以yylval傳送至Yacc。

至於加號，由於加號本身就是字串類型，所以我們直接把”+”號回傳就可以了，型別即為char pointer。

範例 - 簡易計算機1 (1 of 3)

說明

請實作出一個簡易的計算機，計算出兩個正整數的加法，並回傳結果。

本範例分成以下三部分：

1. 完成Lex檔案的實作 (本日目標)
2. 完成Yacc檔案的實作
3. 完成主程式的實作

程式實作

Definitions

在這個範例中，我們會將主程式單獨寫在一個獨立的檔案中，故我們在此匯入主程式的標頭檔。

另外，我們會從"yacc.tab.h"中匯入token的宣告。

我們也在此定義正整數與空白的regular expression。

%{
#include "main.h"
#include "yacc.tab.h"
%}

posint      ([0-9]+)
blank_chars ([ \f\r\t\v]+)

Rules

當我們讀取到正整數的時候，要將其轉成int型別，並且回傳token。我們把這個token命名為NUM_T。

讀取到+號時，則直接回傳+號。

%%

{posint}        { yylval = atoi(yytext); return NUMBER; }
"+"             { return yytext[0]; }
{blank_chars}   { ; }
\n              { ; }

Subroutines

由於我們將主程式移到另一個檔案了，這邊就只要寫yywrap。

%%

int yywrap(void) {
    return 1;
}

到這裡，我們就完成lex檔案的程式撰寫了。

完整程式碼

%{
#include "main.h"
#include "yacc.tab.h"
%}

posint      ([0-9]+)
blank_chars ([ \f\r\t\v]+)

%%

{posint}        { yylval = atoi(yytext); return NUMBER; }
"+"             { return yytext[0]; }
{blank_chars}   { ; }
\n              { ; }

%%

int yywrap(void) {
    return 1;
}

結語

今天我們成功完成lex的token設定，明天就要正式進入Yacc的世界了~

參考資料

• Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
• Tom Niemann. Lex & Yacc